def bubble_sort(arr):
    """
    冒泡排序算法
    时间复杂度: O(n²)
    空间复杂度: O(1)
    稳定性: 稳定
    """
    n = len(arr)
    
    # 外层循环控制排序轮数
    for i in range(n-1):
        # 设置标志位，如果一轮中没有交换，说明已经有序
        swapped = False
        
        # 内层循环进行相邻元素比较和交换
        # 每轮排序后，最大的元素会"冒泡"到末尾
        # 因此下一轮可以少比较一个元素
        for j in range(0, n - i - 1):
            # 如果前一个元素大于后一个元素，则交换
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        
        # 如果这一轮没有发生交换，说明数组已经有序，可以提前退出
        if not swapped:
            break
    
    return arr


def bubble_sort_optimized(arr):
    """
    优化版冒泡排序
    记录最后一次交换的位置，下一轮只需要比较到该位置
    """
    n = len(arr)
    last_swap = n - 1
    
    while last_swap > 0:
        current_swap = 0
        
        for j in range(last_swap):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                current_swap = j
        
        last_swap = current_swap
    
    return arr


def print_array(arr, title=""):
    """打印数组"""
    if title:
        print(f"{title}: {arr}")
    else:
        print(arr)


# 测试用例
if __name__ == "__main__":
    print("=== 冒泡排序演示 ===\n")
    
    # 测试用例1：普通数组
    test1 = [64, 34, 25, 12, 22, 11, 90]
    print_array(test1, "原始数组")
    sorted1 = bubble_sort(test1.copy())
    print_array(sorted1, "排序后")
    print()
    
    # 测试用例2：已排序数组
    test2 = [1, 2, 3, 4, 5]
    print_array(test2, "已排序数组")
    sorted2 = bubble_sort(test2.copy())
    print_array(sorted2, "排序后")
    print()
    
    # 测试用例3：逆序数组
    test3 = [5, 4, 3, 2, 1]
    print_array(test3, "逆序数组")
    sorted3 = bubble_sort(test3.copy())
    print_array(sorted3, "排序后")
    print()
    
    # 测试用例4：包含重复元素的数组
    test4 = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
    print_array(test4, "包含重复元素的数组")
    sorted4 = bubble_sort(test4.copy())
    print_array(sorted4, "排序后")
    print()
    
    # 测试用例5：空数组
    test5 = []
    print_array(test5, "空数组")
    sorted5 = bubble_sort(test5.copy())
    print_array(sorted5, "排序后")
    print()
    
    # 测试用例6：单元素数组
    test6 = [42]
    print_array(test6, "单元素数组")
    sorted6 = bubble_sort(test6.copy())
    print_array(sorted6, "排序后")
    print()
    
    # 性能测试
    import random
    import time
    
    # 生成大数组进行性能测试
    large_array = [random.randint(1, 1000) for _ in range(1000)]
    print("性能测试：1000个随机数的排序")
    
    # 测试标准冒泡排序
    start_time = time.time()
    bubble_sort(large_array.copy())
    standard_time = time.time() - start_time
    print(f"标准冒泡排序耗时: {standard_time:.4f} 秒")
    
    # 测试优化版冒泡排序
    start_time = time.time()
    bubble_sort_optimized(large_array.copy())
    optimized_time = time.time() - start_time
    print(f"优化版冒泡排序耗时: {optimized_time:.4f} 秒")
    
    print(f"\n优化版比标准版快: {standard_time/optimized_time:.2f} 倍") 